Структура даних Черга

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ

Інформація про роботу

Рік:
2011
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
КІ

Частина тексту файла

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 4 Структура даних Черга 1 Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги.Набуття практичних навичок побудовичерги, дослідженнядинаміки її вмісту та використання черг для розв'язання прикладних задач. 2 Постановка задачі: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full)або деком (push_left, push_right, pop_left, pop_right, front_left, front_right,empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queueunderflow) і "переповнення черги" (queueoverflow) або "втрати значимості деку"(dequnderflow) і "переповнення деку" (deqoverflow). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. Змоделювати дек, в якому до опису деку додано дві функціїcommute_leftта commute_right, якізаміняють елемент, що знаходиться в кінці деку (правому або лівому відповідно), на заданий елемент. Кожний раз, коли після операції додаванняв лівому або в правому кінці деку опиниться число більше за 50, то треба зменшити його значення на 10. Після обробки всієї заданої вхідної послідовності перевірити, чи буде дек “дзеркальним” (тобто перший елемент буде дорівнювати останньому, другий – передостанньому і т.д.). ). 3 Алгоритм роз’вязку задачі: Дек організовуємо у вигляді класу. Це дає можливість працювати з усіма типами даних. Спочатку по черзі вносимо елементи. Дані вносяться в дек з права якщо елемент додатній та парний і вносяться з ліва якщо елемент не парний, а якщо елемент від’ємний парний то він робить оперекію pop з права, не парний то з ліва. 4.Динаміка вмісту деку: Внесення в основний дек вхідних даних(п– правий край, л – лівий край) 1)push_left(5) 5           2)push_left(9) 9 5          3)push_right(14) 9 5 14         4)push_right(54); 9 5 14 54        5)push_left(63) 63 9 5 14 54       6)push_right (4) 63 9 5 14 54 4      7)pop_left(-3) 9 5 14 54 4       8)push_left(5) 5 9 5 14 54 4      9)pop_right (-6) 5 9 5 14 54       10)push_left(5) 5 5 9 5 14 54       Перевірка на дзеркальність: 5≠44 5≠14 9≠5 Отже дек не дзеркальний. If (top-left()==top.right()) Pop_left(); pop_right(); 5 Результати виконання програми: / Висновки: На цій лабораторній роботі я ознайомилась зcтруктурою даних черга. А саме із різновидом черги – дек. Дослідила принципи і методи роботи з чергою та деком. Додатки: #include<stdio.h> #include<iostream> #include<conio.h> usingnamespace std; class deq{ private: int left,right; int count; int *items; int Capacity; public: deq(int n){ Capacity = n; items = newint[Capacity]; count = 0; left = Capacity / 2; right = left - 1; } ~deq(){delete[] items;} void push_right(int it){ if (count < Capacity){ if(right == Capacity - 1 ){ for (int i = left - 1; i < right; i++) items[i]=items[i + 1]; items[right] = it; left--; } else items[++right] = it; count++; } } void push_left(int it){ if (count < Capacity){ if(left == 0){ for (int i = right + 1; i > 0; i--) items[i] = items[i - 1]; items[left] = it; right++; } else items[--left] = it; count++; } } int size(){return count;} bool emp...
Антиботан аватар за замовчуванням

18.11.2012 16:11

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини